package demo.DataStrucAndAlgo.Stack;

import java.util.Scanner;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/24-07-24-8:46
 * @Description：demo.DataStrucAndAlgo.Stack     链表模拟栈
 * 栈（stack），先入后出的有序列表，变化的一段称为栈顶（top），固定的一段称为栈底（bottom），入栈（push），出栈（pop）
 * 链表为储存结构，可以无限添加，不用事先指定栈大小；为了逆向打印方便，使用双向链表
 */
class DoubleNode{
    public int data;
    public DoubleNode next;          //保存下一个结点
    public DoubleNode pre;           //保存上一个结点
    public DoubleNode(int data){
        this.data = data;
    }

    @Override
    public String toString() {
        return "DoubleNode{" +
                "data=" + data +
                '}';
    }
}
class DoubleLinkedListStack{
    private DoubleNode root = new DoubleNode(0);    //创建根节点
    public DoubleNode getRoot(){
        return this.root;
    }
    public void push(int data){           //普通add：不按序号存储
        DoubleNode temp = root;            //root不能动，需要辅助结点
        while(temp.next != null){          //查找链表最后结点
            temp = temp.next;
        }
        DoubleNode node = new DoubleNode(data);
        temp.next = node;          //尾结点双向添加
        node.pre = temp;
    }
    public int pop(){
        if(root.next == null){           //判断是否为空链表
            System.out.println("当前栈为空栈");
            return -1;
        }
        DoubleNode temp = root;
        while(temp.next != null){       //遍历到链表最后
            temp = temp.next;
        }
        System.out.println(temp);
        temp = temp.pre;      //删除
        temp.next = null;
        return temp.data;
    }
    public void show(){        //逆向打印
        if(root.next == null){        //判断是否为空链表
            System.out.println("空栈");
            return;
        }
        DoubleNode temp = root;
        while(temp.next != null){           //遍历到链表最后
            temp = temp.next;
        }
        while(temp != root){          //逆向打印
            System.out.println(temp);
            temp = temp.pre;
        }
    }
}
public class stack_linked {
    public static void main(String[] args) {
        DoubleLinkedListStack stack = new DoubleLinkedListStack();
        char key = ' ';//用户输入
        boolean flag = true;//循环判据
        Scanner scanner = new Scanner(System.in);
        while (flag) {
            System.out.println("s(show):打印栈");
            System.out.println("p(push):压栈");
            System.out.println("g(pop):出栈");
            System.out.println("e(exit):退出程序");
            key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    stack.show();
                    break;
                case 'p':
                    System.out.print("请输入数据：");
                    stack.push(scanner.nextInt());
                    break;
                case 'g':
                    stack.pop();
                    break;
                case 'e':
                    flag = false;
                    break;
            }
        }
        scanner.close();
    }
}
